from typing import List
from collections import Counter
import pandas as pd

# ---------------------------------------------------------------------------- #
#                                      状态                                    #
# ---------------------------------------------------------------------------- #
class State:
    def __init__(self):
        self.cards = 1              # 剩余抽卡数
        self.magic: int = 0         # 魔力消耗
        self.damage: float = 0.0    # 伤害倍率
        self.mutiple: int = 1       # 下个模块需要执行的次数

    def __str__(self):
        return f"剩余抽卡数:{self.cards}\t当前法力消耗: {self.magic}\t当前伤害倍率: {self.damage}"

    def __repr__(self):
        return self.__str__()


# ---------------------------------------------------------------------------- #
#                                      模块                                     #
# ---------------------------------------------------------------------------- #
class Module:
    def __init__(self, name: str, additional: int = 1, next_repeat: int = 1, magic_offset: int = 0, damage_offset: float = 0.0):

        self.name = name                        # 模块名称
        self.additional = additional            # 额外施法
        self.next_repeat = next_repeat          # 下个法术重复施法次数
        self.magic_offset = magic_offset        # 魔力修正
        self.damage_offset = damage_offset      # 伤害修正

        # 隐藏属性，最终需要执行的次数
        self.mutiple = 1

    # 执行一个模块
    def forward(self, state: State):
        if self.next_repeat > 1:                                        # 当前模块是重复施法模块，不影响抽卡，魔力和伤害
            state.mutiple *= self.next_repeat
        else:
            # 非重复施法，执行次数为 state.mutiple
            self.mutiple = state.mutiple
            state.mutiple = 1
            state.cards += (self.additional - 1) * self.mutiple       # 额外施法
            state.magic += self.magic_offset * self.mutiple           # 魔力修正
            state.damage += self.damage_offset * self.mutiple         # 伤害修正


    # 撤销一个模块的执行，DFS回溯
    def undo(self, state: State) -> State:
        if self.next_repeat > 1:
            state.mutiple //= self.next_repeat
        else:
            state.cards -= (self.additional - 1) * self.mutiple       # 额外施法
            state.magic -= self.magic_offset * self.mutiple           # 魔力修正
            state.damage -= self.damage_offset * self.mutiple         # 伤害修正
            state.mutiple = self.mutiple
            self.mutiple = 1

# ---------------------------------------------------------------------------- #
#                                     模块卡池                                  #
# ---------------------------------------------------------------------------- #
class ModulePool:
    __module_args_list: List[dict] = [
        {"name": "二次重复施法", "additional": 1, "next_repeat": 2},
        {"name": "三次重复施法", "additional": 1, "next_repeat": 3},
        {"name": "四次重复施法", "additional": 1, "next_repeat": 4},
        {"name": "六次重复施法", "additional": 1, "next_repeat": 6},

        {"name": "注魔20", "additional": 0, "magic_offset": -20},
        {"name": "注魔40", "additional": 0, "magic_offset": -40},
        {"name": "注魔60", "additional": 0, "magic_offset": -60},
        {"name": "注魔80", "additional": 0, "magic_offset": -80},
        {"name": "注魔100", "additional": 0, "magic_offset": -100},

        {"name": "双重施法", "additional": 2, "magic_offset": 2},
        {"name": "三重施法", "additional": 3, "magic_offset": 4},
        {"name": "六重施法", "additional": 6, "magic_offset": 8},
        {"name": "八重施法", "additional": 8, "magic_offset": 20},

        {"name": "伤害小幅加强", "additional": 1, "magic_offset": 5, "damage_offset": 1.1},
        {"name": "伤害中幅加强", "additional": 1,
            "magic_offset": 12, "damage_offset": 1.2},
        {"name": "伤害大幅加强", "additional": 1,
            "magic_offset": 40, "damage_offset": 1.5},
    ]
    __module_args_map = {m["name"]: m for m in __module_args_list}

    @staticmethod
    def get_module_by_name(module_name: str) -> Module:
        return Module(**ModulePool.__module_args_map[module_name])

    @staticmethod
    def get_module_by_name_list(module_name_list: List[str]) -> List[Module]:
        return [ModulePool.get_module_by_name(m) for m in module_name_list]

# ---------------------------------------------------------------------------- #
#                                    执行一系列模块                             #
# ---------------------------------------------------------------------------- #
def execute(name_list: List[str]):
    module_list = ModulePool().get_module_by_name_list(name_list)
    state = State()
    df = {
        "法术名称": [],
        "施放次数": [],
        "剩余抽卡数": [],
        "魔力消耗": [],
        "伤害倍率": [],
    }
    for idx, m in enumerate(module_list):
        m.forward(state)
        df["法术名称"].append(m.name)
        df["施放次数"].append(m.mutiple)
        df["剩余抽卡数"].append(state.cards)
        df["魔力消耗"].append(state.magic)
        df["伤害倍率"].append(state.damage)
    df = pd.DataFrame(df)
    pd.set_option('display.unicode.east_asian_width', True)
    print(df)

# ---------------------------------------------------------------------------- #
#                                 从一系列模块中找出最佳方案                     #
# ---------------------------------------------------------------------------- #
def optimizer(modules: List[str], slots_num: int):
    max_damage = 0
    results = []
    output_list = []

    def dfs(counter: dict, state: State, index: int, max_index: int):
        nonlocal max_damage
        nonlocal results
        if index >= max_index:
            
            # 剩余抽卡数大于0，且剩余魔力消耗小于0，且伤害为历史新高，代表新的最佳方案出现，进行记录
            if state.damage > max_damage and state.cards >= 0 and state.magic <= 0:
                results = output_list[:]
                max_damage = state.damage
            return

        if state.cards <= 0:                 # 当剩余抽卡数为0时，中断施法
            return

        # 递归与回溯
        for name, num in counter.items():
            if num > 0:
                counter[name] -= 1
                module = ModulePool.get_module_by_name(name)
                module.forward(state)
                output_list.append(name)
                dfs(counter, state, index + 1, max_index)
                output_list.pop()
                module.undo(state)
                counter[name] += 1

    dfs(dict(Counter(modules).most_common()), State(), 0, slots_num)
    execute(results)


if __name__ == "__main__":
    name_list = [
        "六次重复施法",
        "六次重复施法",
        "八重施法",
        "三次重复施法",
        "三次重复施法",
        "六次重复施法",
        "三次重复施法",
        "注魔100",
        "三次重复施法",
        "三次重复施法",
        "三次重复施法",
        "三次重复施法",
        "伤害大幅加强",
    ]

    print("# ------------------------------------ 优化前 ----------------------------------- #")
    execute(name_list)
    print()
    print("# ------------------------------------ 优化后 ----------------------------------- #")
    optimizer(name_list, 13)
